/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/9 20:39
 */
// 生成随机数
    // https://leetcode.cn/problems/implement-rand10-using-rand7/description/
    // 【步骤】
//
//1 下面将需要生成的随机数中最大值记为n
//
//2 先去生成一个等概率产生0和1的方法：rand2() 。
//
//不要去纠结为什么返回值不是1和2，因为方便二进制位运算。
//3 实现：调用 rand7() ，1,2,3 返回1，4,5,6 返回2，7 重来。
//将n转为二进制，看看是几位的二进制。
//
//例如本题的 10 ，二进制为 1010 。也就是说仅仅需要4位二进制数就能表示10进制的10。 用这个 rand2() 方法生成n的每个二进制位。
//4 创建一个数为 rand2() ，每次左移一位再加 rand2() 。
//
//5 如果出现不符合题意的情况，再次调用 rand10() 。
//
//例如如上步骤可能生成 0000 , 1011 、…… 、1111 （分别为0,11、 …… 、15），显然这些都是不在[1,10]中的正整数，所以只能重新生成。
public class Solution470 extends SolBase {
    public int rand10() {
        int ans = rand2();
        for (int i = 0; i < 3; i++) {
            ans <<= 1;
            ans ^= rand2();
        }
        return (ans <= 10 && ans > 0) ? ans : rand10();
    }

    private int rand2() {
        int ans = rand7();
        return ans == 7 ? rand2() : ans % 2;
    }
}
